package primary.code05_Tree;


/**
 * leetcode  https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/description/
 * @author Yudi Wang
 * @date 2021/7/12 18:46
 * <p>
 * 查找公共祖先节点
 * 两种情况：1 互为最低公共祖先  2 汇聚于其他节点
 */
public class Code08_LowestCommonNode {

    private static Node findLowestCommonNode(Node head, Node o1, Node o2) {
        //遇到 null o1 o2 则返回
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        //后续遍历节点
        Node left = findLowestCommonNode(head.left, o1, o2);
        Node right = findLowestCommonNode(head.right, o1, o2);
        /*左和右都不为null---说明在左子树中发现过n1或n2，
         * 在右子树上也发现过n1或n2，并且n1和n2在当前节点首次相遇
         */
        if (left != null && right != null) {
            return head;
        }
        /*左和右中一个不为null，另一个为null，
         * 说明不为null的节点是n1或n2中的一个，或者是n1和n2的最近祖先；
         * 直接返回；
         */
        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }
        //左和右均为null，没有发现n1和n2；
        return null;
    }

    private static Node findLowestCommonNodeTest(Node head, Node o1, Node o2) {
        if (head == null || head == o1 || head == o2) return head;
        Node left = findLowestCommonNodeTest(head.left, o1, o2);
        Node right = findLowestCommonNodeTest(head.right, o1, o2);
        if (left != null && right != null) {
            return head;
        }
        if (left == null && right == null) {
            return null;
        }
        return left != null ? left : right;
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.right.left = new Node(7);
        head.right.right = new Node(9);
        head.right.right.right = new Node(10);

        Node lcn1 = findLowestCommonNode(head, head.right.left, head.right.right.right);
        Node lcn2 = findLowestCommonNodeTest(head, head.right.left, head.right.right.right);
        System.out.println(lcn1 != null ? lcn1.data : null);
        System.out.println(lcn2 != null ? lcn2.data : null);
    }
}
